﻿// MnemonicStack.cs
//
// Copyright 2008 by Burt Harris
// Licensed under the Microsoft Public License (Ms-PL)
// See: http://www.codeplex.com/yaml/license
//

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.Globalization;

namespace YaTools.Yaml
{
    // Factor out the size of indexes
    using M = Int16;

    [ContractVerification(false)]
    internal sealed class MnemonicStack<T> : IEnumerable<T>
        where T : IEquatable<T>, new()
    {
        private readonly List<T> _list;
        private int _count;
        private List<M> _links;
        private M _memorized = -1;
        private M _mnemonicKey;
        private const M SizeThreshold = M.MaxValue/2;
        private M _top = -1;

        public MnemonicStack() : this(32)
        {
        }

        //
        // Summary:
        //     Initializes a new instance of the YaTools.Yaml.MnemonicStack<T> class
        //     that is empty and has the specified initial capacity or the default initial
        //     capacity, whichever is greater.
        //
        // Parameters:
        //   capacity:
        //     The initial number of elements that the YaTools.Yaml.MnemonicStack<T>
        //     can contain.
        //
        // Exceptions:
        //   System.ArgumentOutOfRangeException:
        //     capacity is less than zero.
        public MnemonicStack(int capacity)
        {
            Contract.Requires<ArgumentOutOfRangeException>(capacity >= 0, "capacity");
            _list = new List<T>(capacity);
        }

        [ContractInvariantMethod]
        private void ObjectInvariant()
        {
            Contract.Invariant(_list != null);
        }

        public int Count
        {
            get { return _count; }
        }

        #region IEnumerable<T> Members

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        /// <summary>
        /// Memorizes the current state of the stack and an additional item of type T
        /// </summary>
        /// <param name="item">The extra item to be memorized</param>
        /// <returns>An mnemonic device which can later be passed to Recall()</returns>
        public M Memorize(T item)
        {
            EnsureMnemonic();
            M hold = _top; // Remeber current top of stack
            Intern(item);
            try
            {
                _memorized = Math.Max(_memorized, _top);
                return EncodeMnemonic(_top);
            }
            finally
            {
                _top = hold; // Logically pop it back off the stack                
            }
        }

        /// <summary>
        /// Returns the stack to a state Memorized in the past.
        /// </summary>
        /// <param name="mnemonic">The mnemonic value returned from Memorize()</param>
        /// <returns>The extra item passed to Memorize</returns>
        public T Recall(M mnemonic)
        {
            EnsureMnemonic();
            Seek(DecodeMnemonic(mnemonic));
            return Pop();
        }

        private void EnsureMnemonic()
        {
            if (_links == null)
            {
                _links = new List<M>(Count);
                for (M i = 0; i < Count; i++)
                    _links.Add((M) (i - 1));
                _top = (M) (_links.Count - 1);
            }
            Assert(_list.Count == _links.Count);
        }


        private void Intern(T item)
        {
            // Since we are capturing not only the item, but the 
            // state of the stack at this time (as represented by _top), 
            // we can optimize the search by starting at _top, since
            // no location in the collection below it could have it is a previous
            // location.  We stop searching at the highest location that's
            // been Memorized, so that we don't capture states we don't need;
            M start = Math.Max((M) 0, _top);
            M end = Math.Max(_top, _memorized);

            for (M i = start; i <= end; i++)
                if (_links[i] == _top && _list[i].Equals(item))
                {
                    _top = i; // Mark as new top
                    return; // No need to add it again
                }
            if (++end == _list.Count)
            {
                _list.Add(item);
                _links.Add(_top);
            }
            else
            {
                _list[end] = item; // Record the item being interned in the next slot
                _links[end] = _top; // Record previous top
            }
            _top = end; // Mark as new top
        }

        private void Seek(M mnemonic)
        {
            EnsureMnemonic();
            if (mnemonic == 0 && _list.Count == 0)
                _top = -1;
            else
            {
                if (mnemonic != 0 && (mnemonic < 0 || mnemonic >= _list.Count))
                    throw new ArgumentOutOfRangeException("mnemonic");
                _top = mnemonic;
            }
            _count = CalculateCount();
        }

        private int CalculateCount()
        {
            int count = 0;
            for (int i = _top; i >= 0; i = _links[i])
                count++;
            return count;
        }

        // Summary:
        //     Initializes a new instance of the YaTools.Yaml.MnemonicStack<T> class
        //     that is empty and has the default initial capacity.

        // Summary:
        //     Removes all objects from the YaTools.Yaml.MnemonicStack<T>.
        public void Clear()
        {
            _count = 0;
            if (_links == null) _list.Clear();
            else _top = -1;
        }

        //
        // Summary:
        //     Determines whether an element is in the YaTools.Yaml.MnemonicStack<T>.
        //
        // Parameters:
        //   item:
        //     The object to locate in the YaTools.Yaml.MnemonicStack<T>. The value
        //     can be null for reference types.
        //
        // Returns:
        //     true if item is found in the YaTools.Yaml.MnemonicStack<T>; otherwise,
        //     false.

        public bool Contains(T item)
        {
            using (Enumerator e = GetEnumerator())
            {
                while (e.MoveNext())
                    if (e.Current.Equals(item))
                        return true;
                return false;
            }
        }

        //
        // Summary:
        //     Copies the YaTools.Yaml.MnemonicStack<T> to an existing one-dimensional
        //     System.Array, starting at the specified array mnemonic.
        //
        // Parameters:
        //   array:
        //     The one-dimensional System.Array that is the destination of the elements
        //     copied from YaTools.Yaml.MnemonicStack<T>. The System.Array must have
        //     zero-based indexing.
        //
        //   arrayIndex:
        //     The zero-based mnemonic in array at which copying begins.
        //
        // Exceptions:
        //   System.ArgumentNullException:
        //     array is null.
        //
        //   System.ArgumentOutOfRangeException:
        //     arrayIndex is less than zero.
        //
        //   System.ArgumentException:
        //     arrayIndex is equal to or greater than the length of array.-or-The number
        //     of elements in the source YaTools.Yaml.MnemonicStack<T> is greater
        //     than the available space from arrayIndex to the end of the destination array.
        public void CopyTo(T[] array, int arrayIndex)
        {
            if (array == null)
                throw new ArgumentNullException("array");
            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException("arrayIndex");
            using (Enumerator e = GetEnumerator())
            {
                if (arrayIndex + e.Count > array.Length)
                {
                    throw new ArgumentException(
                        String.Format(CultureInfo.InvariantCulture,
                                      "Insuffient space in array, stack size: {0}, array size: {1}, array mnemonic {2}",
                                      e.Count, array.Length, arrayIndex));
                }

                while (e.MoveNext())
                    array[arrayIndex++] = e.Current;
            }
        }

        //
        // Summary:
        //     Returns an enumerator for the YaTools.Yaml.MnemonicStack<T>.
        //
        // Returns:
        //     An YaTools.Yaml.MnemonicStack<T>.Enumerator for the YaTools.Yaml.MnemonicStack<T>.
        private Enumerator GetEnumerator()
        {
            return new Enumerator(this);
        }

        //
        // Summary:
        //     Returns the object at the top of the YaTools.Yaml.MnemonicStack<T>
        //     without removing it.
        //
        // Returns:
        //     The object at the top of the YaTools.Yaml.MnemonicStack<T>.
        //
        // Exceptions:
        //   System.InvalidOperationException:
        //     The YaTools.Yaml.MnemonicStack<T> is empty.
        public T Peek()
        {
            if (_count <= 0) throw new InvalidOperationException("Stack is empty");
            if (_links == null) return _list[_list.Count - 1];
            return _list[_top];
        }

        //
        // Summary:
        //     Removes and returns the object at the top of the YaTools.Yaml.MnemonicStack<T>.
        //
        // Returns:
        //     The object removed from the top of the YaTools.Yaml.MnemonicStack<T>.
        //
        // Exceptions:
        //   System.InvalidOperationException:
        //     The YaTools.Yaml.MnemonicStack<T> is empty.
        public T Pop()
        {
            T item = Peek();

            if (_links != null) _top = _links[_top];
            else _list.RemoveAt(_list.Count - 1);

            _count--;
            return item;
        }

        //
        // Summary:
        //     Inserts an object at the top of the YaTools.Yaml.MnemonicStack<T>.
        //
        // Parameters:
        //   item:
        //     The object to push onto the YaTools.Yaml.MnemonicStack<T>. The value
        //     can be null for reference types.
        public void Push(T item)
        {
            if (_links == null) _list.Add(item);
            else Intern(item);
            _count++;
        }

        //
        // Summary:
        //     Copies the YaTools.Yaml.MnemonicStack<T> to a new array.
        //
        // Returns:
        //     A new array containing copies of the elements of the YaTools.Yaml.MnemonicStack<T>.
        public T[] ToArray()
        {
            if (_links == null) return _list.ToArray();
            return new List<T>(this).ToArray();
        }

        /// <summary>
        ///     If the underlying _list is getting large, reclaims storage.  
        /// </summary>
        /// <remarks>
        ///    Reclaimation can only occur when the logical stack is empty,
        ///    so it generally makes sense to call this after a Recall(0)
        ///
        ///    If a reset occurs, this will invalidate all mnemonic indices, 
        ///    and the sign of future Remembered indices will change to indicate
        ///    they are a distinct set of values.
        /// </remarks>
        public void TrimExcess()
        {
            if (_links == null)
                _list.TrimExcess();
            else if (_top == -1)
            {
                if (Count == 0 && _list.Count >= SizeThreshold)
                {
                    // Special case, we can reset the item list now if we need to
                    // and force rescan the file by flipping the sign bit on the indexes.
                    _mnemonicKey ^= M.MinValue;
                    _memorized = -1;
                    _list.Clear();
                    _list.TrimExcess();
                    _links.Clear();
                    _links.TrimExcess();
                }
            }
        }

        // Summary:
        //     Enumerates the elements of a YaTools.Yaml.MnemonicStack<T>.

        [Conditional("DEBUG")]
        private static void Assert(bool condition)
        {
            // Non-coverage oth this throw isn't that bad...
            if (!condition)
                throw new InvalidOperationException("Unexpected condition detected");
        }

        private M EncodeMnemonic(M link)
        {
            return (M) (link ^ _mnemonicKey);
        }

        private M DecodeMnemonic(M link)
        {
            return (M) (link ^ _mnemonicKey);
        }

        #region Nested type: Enumerator

        private struct Enumerator : IEnumerator<T>
        {
            private readonly M[] _indices;
            private readonly MnemonicStack<T> _stack; // Underlying MnemonicStack
            private int _state;

            public Enumerator(MnemonicStack<T> stack)
            {
                if (stack == null) throw new ArgumentNullException("stack");

                _state = -1;
                this._stack = stack;
                if (stack._links == null) _indices = null;
                else
                {
                    int size = stack.Count; // Size array to current logical count
                    _indices = new M[size];
                    M link = stack._top;

                    for (int i = 0; i < size; i++)
                    {
                        _indices[size - i - 1] = link;
                        link = stack._links[link];
                    }
                    Assert(link == -1);
                }
            }

            public int Count
            {
                get
                {
                    if (_indices == null) return _stack.Count;
                    return _indices.Length;
                }
            }

            // Summary:
            //     Gets the element at the current position of the enumerator.
            //
            // Returns:
            //     The element in the YaTools.Yaml.MnemonicStack<T> at the current position
            //     of the enumerator.
            //
            // Exceptions:
            //   System.InvalidOperationException:
            //     The enumerator is positioned before the first element of the collection or
            //     after the last element.

            #region IEnumerator<T> Members

            public T Current
            {
                get
                {
                    if (_indices == null)
                    {
                        if (_state < 0 || _state > _stack._list.Count)
                            throw new InvalidOperationException("Enumerator not positioned on an element");
                        return _stack._list[_state];
                    }
                    if (_state < 0 || _state > _indices.Length)
                        throw new InvalidOperationException("Enumerator not positioned on an element");
                    return _stack._list[_indices[_state]];
                }
            }

            //
            // Summary:
            //     Advances the enumerator to the next element of the YaTools.Yaml.MnemonicStack<T>.
            //
            // Returns:
            //     true if the enumerator was successfully advanced to the next element; false
            //     if the enumerator has passed the end of the collection.
            //
            // Exceptions:
            //   System.InvalidOperationException:
            //     The collection was modified after the enumerator was created.

            public bool MoveNext()
            {
                return ++_state < Count;
            }

            public void Dispose()
            {
            }

            object IEnumerator.Current
            {
                get { return Current; }
            }

            public void Reset()
            {
                _state = -1;
            }

            #endregion
        }

        #endregion
    }
}